The present invention relates generally to computer systems and more particularly, to computer systems for use in a warehouse environment.
In recent years, ever more attention has been paid to efficient allocation of items in supply management systems. Such systems, which can include warehouse management systems, supply chain management systems, inventory management systems, enterprise resource planning systems, and the like, all are dedicated to allowing organizations to more efficiently allocate scarce resources among competing purposes. Merely by way of example, modern warehouse management systems (“WMS”) often are complex software packages that run on top of a relational database management system (“RDBMS”), such as the Oracle 10g™ RDBMS. Oracle Warehouse Management™ is one example of such a package.
One goal of a WMS application is to most efficiently allocate bulk items. As a simple example, if a customer orders 5200 linear feet of a particular material with a tolerance of ±100 feet, and the material is available in rolls of 250 linear feet, a WMS might allocate 21 rolls of the material to the order, resulting in an overallocation of 50 linear feet, which falls within the customer's tolerance. In many cases, however, the task of allocation is not so simple. Merely by way of example, items often are available in a variety of sizes, so that, in the example above, there might be 10 50-foot rolls, 20 60-foot rolls, and 15 100-foot rolls of the material available. Even this example is over-simplified, however, since most real manufacturing and/or warehousing environments will have thousands of items (such as rolls, pallets, or drums of material), with substantial variation among the items (in terms of the quantity of material each item contains.
Merely by way of example, in a manufacturing environment with high variability, such as in the manufacture of steel coils, paper rolls, chemicals, etc. there is frequently significant variation in the size of the item (batch, pallet, roll, etc.) that rolls off the manufacturing line. For instance, though one may expect 1000 lbs. of steel per pallet, the variability may mean that sequential items weigh anywhere from 700 lbs. to 1300 lbs. As warehouse processes often require a close match between a material request and the items that are used to fulfill that request, this variability makes it difficult to select the right combination of items that come closest to the requested quantity, particularly when the request itself also allows variability. For instance, if a customer ordered 13,700 lbs. of steel, but allows over- or under-shipment of up to 4%, finding an optimal allocation of pallets presents a non-trivial problem. The problem is further complicated because “optimal” can be defined in a variety of ways. Merely by way of example, one optimal solution might be the selection of items that come closest to the requested quantity but, under no circumstances exceeds the upper tolerance. Another optimal solution, however might seek to minimize the total number of items that fall within the requested tolerance.
Typically, this problem is addressed in one of three ways. First, it can be modeled as a binary programming problem, with costs attached to number of items and the deviation of the solution from the requested quantity. These weights can be varied depending on the type of solution desired, and then the entire problem can be solved using the branch-and-bound variation of the simplex algorithm. While this approach often produces highly accurate solutions, it is computation-intensive and often is unacceptably slow when the number of items is large, which makes it unusable when hundreds or thousands of separate material requests need to be allocated in a short period.
An alternate approach is to use a very simplistic heuristic, allocating items in a “greedy” fashion in some basic user- or system-defined sequence, such as largest items first, until no more items can be added. While this approach tends to require relatively low computation power, it often produces low quality solutions that are not necessarily either the fewest number of items, or very close to the requested quantity.
As a third approach, if the tolerances and desire to reduce the number of items allocated can be ignored, the allocation of items can be modeled as a classical optimization problem called the “subset-sum” problem, where the goal is to find the subset of numbers among a larger set of numbers whose sum is the largest possible amount, so long as it is equal to or below a certain target value. There has been considerable research into the subset-sum problem, and many successful heuristics have been developed using this approach. As noted above, however, the subset-sum approach does not account either for tolerances in the target value or for the need to minimize total numbers used, however, and thus fails to produce optimal solutions in a typical manufacturing/warehousing environment, in which customers often tolerate variation from a stated order size, and in which efficiency concerns often dictate that a minimum number of items be allocated to any given order.
Hence, there is a need in the art for more robust methods and systems for allocating items.